package HighMethod08;

/**
 * 动态规划求解01背包问题
 */
public class Package01Dynamic {

    public static void main(String[] args) {
        int n = 5;       //物品个数
        int c = 10;     //背包容量
        int[] W = {2, 2, 6, 5, 4};
        int[] V = {6, 3, 5, 4, 6};
        int maxV = funDynamic(W, V, c);
        System.out.println("01背包能装物品的最大价值总和:" + maxV);
    }

    //非递归，但是还是穷举，时间复杂度还是很高，实际情况一定需要很多剪枝
    private static int funDynamic(int[] w, int[] v, int c) {
        int len = w.length;
        int[] br = new int[len];
        int i = 0;
        br[i] = -1;
        int maxv = 0;
        while (i >= 0) {             //以下的分支条件判断是回溯法的一种通用形式
            br[i] += 1;
            if (br[i] == 2) {
                i = i - 1;
            } else if (i == len - 1) {
                int t = Print_Ar(br, w, v, c);
                maxv = Math.max(t, maxv);
            } else {
                i = i + 1;
                br[i] = -1;
            }
        }
        return maxv;
    }

    private static int Print_Ar(int[] br, int[] w, int[] v, int c) {
        int len = w.length;
        int maxv = 0;
        for (int i = 0; i < len; i++) {
            maxv += br[i] * v[i];
            c -= br[i] * w[i];
            if (c < 0) {
                return 0;
            }
        }
        return maxv;
    }
}
